public class LC322 {
    public int coinChange(int[] coins, int amount) {
        int length = coins.length;
        if(amount==0)
            return -1;
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int i = 1; i <= amount; i++) {
            int minValue = Integer.MAX_VALUE;
            for (int coin : coins) {
                if (i >= coin) {
                    int subCoins = i - coin;
                    if(subCoins==0){
                        minValue=0;
                    }
                    else if (dp[subCoins] != 0 && dp[subCoins] < minValue) {
                        minValue = dp[subCoins];
                    }
                }
            }
            if(minValue<Integer.MAX_VALUE)
                dp[i] = minValue+1;
        }
        if (dp[amount] == 0) {
            return -1;
        }
        return dp[amount];
    }
}
